home *** CD-ROM | disk | FTP | other *** search
/ SGI Developer Toolbox 6.1 / SGI Developer Toolbox 6.1 - Disc 4.iso / public / rsynth / src / trie.c < prev    next >
C/C++ Source or Header  |  1994-08-01  |  1KB  |  77 lines
  1. #include <stdlib.h>
  2. #include <stdio.h>
  3. #include <memory.h>
  4. #include "proto.h"
  5. #include "trie.h"
  6.  
  7. struct trie_s
  8.  {
  9.   struct trie_s *otherwise;
  10.   struct trie_s *more;
  11.   void *value;
  12.   char ch;
  13.  };
  14.  
  15. void trie_insert(r,s,value)
  16. trie_ptr *r;
  17. char *s;
  18. void *value;
  19. {
  20.  trie_ptr p = NULL;
  21.  char ch;
  22.  while ((ch = *s++))
  23.   {
  24.    while ((p = *r))
  25.     {
  26.      if (p->ch == ch)
  27.       break;
  28.      else
  29.       r = &p->otherwise;
  30.     }
  31.    if (!p)
  32.     {
  33.      p     = (trie_ptr) malloc(sizeof(*p));
  34.      memset(p,0,sizeof(*p));
  35.      p->ch = ch;
  36.      *r    = p;
  37.     }
  38.    r = &p->more;
  39.   }
  40.  p->value = value;
  41. }
  42.  
  43. void *trie_lookup(r,sp)
  44. trie_ptr *r;
  45. char **sp;
  46. {char *s     = *sp;
  47.  char *value = NULL;
  48.  char     ch;
  49.  while ((ch = *s))
  50.   {
  51.    trie_ptr *l = r;
  52.    trie_ptr p;
  53.    while ((p = *l))
  54.     {
  55.      if (p->ch == ch)
  56.       break;
  57.      else
  58.       l = &p->otherwise;
  59.     }
  60.    if (p)
  61.     {
  62.      *l     = p->otherwise;
  63.      p->otherwise = *r;
  64.      *r    = p;
  65.      r     = &p->more;
  66.      value = p->value;
  67.      s++;
  68.     }
  69.    else
  70.     break;
  71.   }
  72.  *sp = s;
  73.  return value;
  74. }
  75.  
  76.  
  77.